// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 包rsa实现PKCS#1和RFC 8017中指定的rsa加密。
// 
// RSA是本软件包中用于实现公钥加密或公钥签名的单一基本操作。
// 
// RSA加密和签名的原始规范是PKCS#1 
// 术语“RSA加密”和“RSA签名”默认指的是
// PKCS#1 1.5版。然而，该规范存在缺陷，新设计
// 应该使用版本2，通常仅由OAEP和PSS调用，其中
// 是可能的。
// 
// 本包包含两套接口。当不需要更抽象的
// 接口时，可以使用v1对
// 进行加密/解密。5/OAEP，并与v1进行签名/验证。5/PSS。如果需要在公钥原语上抽象
// 的话，PrivateKey类型将从加密包中实现
// 解密器和签名器接口。
// 
// 此包中的RSA操作不是使用常数时间算法实现的。
package rsa

import (
	"crypto"
	"crypto/rand"
	"crypto/subtle"
	"errors"
	"hash"
	"io"
	"math"
	"math/big"

	"crypto/internal/randutil"
)

var bigZero = big.NewInt(0)
var bigOne = big.NewInt(1)

// 公钥代表RSA密钥的公共部分。
type PublicKey struct {
	N *big.Int // 模
	E int      // 公共指数
}

// 在PublicKey上实现的任何方法可能也需要在
// PrivateKey上实现，因为后者嵌入了前者并将公开其方法。

// Size返回以字节为单位的模数大小。此公钥的原始签名和密文
// 大小相同。
func (pub *PublicKey) Size() int {
	return (pub.N.BitLen() + 7) / 8
}

// Equal报告pub和x是否具有相同的值。
func (pub *PublicKey) Equal(x crypto.PublicKey) bool {
	xx, ok := x.(*PublicKey)
	if !ok {
		return false
	}
	return pub.N.Cmp(xx.N) == 0 && pub.E == xx.E
}

// OAEPOptions是一个使用
// crypto将选项传递给OAEP解密的接口。解密程序接口。
type OAEPOptions struct {
	// Hash是生成掩码时使用的哈希函数。
	Hash crypto.Hash
	// 标签是一个任意字节字符串，必须等于加密时使用的值
	// 。
	Label []byte
}

var (
	errPublicModulus       = errors.New("crypto/rsa: missing public modulus")
	errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small")
	errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large")
)

// checkPub-sanity在使用公钥之前检查公钥。
// 我们需要酒吧。E来拟合一个32位整数，这样我们
// 就不会有不同的行为，这取决于
// int是32位还是64位。另见
// https:
func checkPub(pub *PublicKey) error {
	if pub.N == nil {
		return errPublicModulus
	}
	if pub.E < 2 {
		return errPublicExponentSmall
	}
	if pub.E > 1<<31-1 {
		return errPublicExponentLarge
	}
	return nil
}

// 私钥代表RSA密钥
type PrivateKey struct {
	PublicKey            // 公共部分。
	D         *big.Int   // 私有指数
	Primes    []*big.Int // N的素因子，有>=2个元素。

	// 预计算包含预计算值，可加速私有
	// 操作（如果可用）。
	Precomputed PrecomputedValues
}

// Public返回priv对应的公钥。
func (priv *PrivateKey) Public() crypto.PublicKey {
	return &priv.PublicKey
}

// Equal报告priv和x的值是否相等。它忽略
// 预计算的值。
func (priv *PrivateKey) Equal(x crypto.PrivateKey) bool {
	xx, ok := x.(*PrivateKey)
	if !ok {
		return false
	}
	if !priv.PublicKey.Equal(&xx.PublicKey) || priv.D.Cmp(xx.D) != 0 {
		return false
	}
	if len(priv.Primes) != len(xx.Primes) {
		return false
	}
	for i := range priv.Primes {
		if priv.Primes[i].Cmp(xx.Primes[i]) != 0 {
			return false
		}
	}
	return true
}

// 与priv签署签名摘要，阅读兰德的随机性。如果opts是
// /*PSS选项，则将使用PSS算法，否则使用PKCS#1 v1。5将使用
// 。摘要必须是使用
// opts对输入消息进行哈希运算的结果。HashFunc（）。
// 
// 此方法实现加密。Signer，这是一个支持密钥
// 的接口，其中私有部分保存在硬件模块中。常用
// 用户应直接使用此软件包中的Sign*函数。
func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
	if pssOpts, ok := opts.(*PSSOptions); ok {
		return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts)
	}

	return SignPKCS1v15(rand, priv, opts.HashFunc(), digest)
}

// Decrypt使用priv解密密文。如果opts为nil或类型为
// *pkcs1v15 Decrypt options，则PKCS#1 v1。5.执行解密。否则
// opts必须具有类型*OAEPOptions，并且OAEP解密已完成。
func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) {
	if opts == nil {
		return DecryptPKCS1v15(rand, priv, ciphertext)
	}

	switch opts := opts.(type) {
	case *OAEPOptions:
		return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label)

	case *PKCS1v15DecryptOptions:
		if l := opts.SessionKeyLen; l > 0 {
			plaintext = make([]byte, l)
			if _, err := io.ReadFull(rand, plaintext); err != nil {
				return nil, err
			}
			if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil {
				return nil, err
			}
			return plaintext, nil
		} else {
			return DecryptPKCS1v15(rand, priv, ciphertext)
		}

	default:
		return nil, errors.New("crypto/rsa: invalid options for Decrypt")
	}
}

type PrecomputedValues struct {
	Dp, Dq *big.Int // D mod（P-1）（或mod Q-1）
	Qinv   *big.Int // Q^-1 mod P 

	// CRT值用于第三个和后续的素数。由于历史事故，前两个素数的CRT在PKCS#1中的处理方式不同，互操作性足够重要，我们需要反映这一点。
	CRTValues []CRTValue
}

// CRTValue包含预计算的中国剩余定理值。
type CRTValue struct {
	Exp   *big.Int // D mod（prime-1）。
	Coeff *big.Int // R·科夫≡ 1模素数。
	R     *big.Int // 在此之前素数的乘积（包括p和q）。
}

// Validate对密钥执行基本的健全性检查。
// 如果密钥有效，则返回nil，否则返回描述问题的错误。
func (priv *PrivateKey) Validate() error {
	if err := checkPub(&priv.PublicKey); err != nil {
		return err
	}

	// 检查∏素数==n.
	modulus := new(big.Int).Set(bigOne)
	for _, prime := range priv.Primes {
		// 任何素数≤ 1将在以后引发除以零的恐慌。
		if prime.Cmp(bigOne) <= 0 {
			return errors.New("crypto/rsa: invalid prime value")
		}
		modulus.Mul(modulus, prime)
	}
	if modulus.Cmp(priv.N) != 0 {
		return errors.New("crypto/rsa: invalid modulus")
	}

	// 检查一下≡ 每个质数对应1个mod p-1。
	// 这意味着e是每个p-1的互质，因为e有一个乘法的
	// 逆。因此e是lcm的互质（p-1，q-1，r-1，…）=
	// 指数(ℤ/Nℤ). 这也意味着≡ a模p为a^（p-1）≡ 1 
	// mod p.因此≡ 一个mod n表示所有的互质到n，根据需要。
	congruence := new(big.Int)
	de := new(big.Int).SetInt64(int64(priv.E))
	de.Mul(de, priv.D)
	for _, prime := range priv.Primes {
		pminus1 := new(big.Int).Sub(prime, bigOne)
		congruence.Mod(de, pminus1)
		if congruence.Cmp(bigOne) != 0 {
			return errors.New("crypto/rsa: invalid exponents")
		}
	}
	return nil
}

// GenerateKey使用
// 随机源random（例如，crypto/rand.Reader）生成给定位大小的RSA密钥对。
func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
	return GenerateMultiPrimeKey(random, 2, bits)
}

// GenerateMultiPrimeKey生成给定位
// 大小和给定随机源的多素数RSA密钥对，如[1]所示。虽然公开的
// 密钥与2素数情况兼容（实际上无法区分），但私钥不兼容。因此，可能无法以某些格式导出多素数
// 私钥，或随后将其导入其他
// 代码。[2]中的表1给出了给定大小的最大素数。
// 
// /[1]美国专利4405829（1972年到期）
// www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) {
	randutil.MaybeReadByte(random)

	priv := new(PrivateKey)
	priv.E = 65537

	if nprimes < 2 {
		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
	}

	if bits < 64 {
		primeLimit := float64(uint64(1) << uint(bits/nprimes))
		// pi近似于小于primeLimit的素数
		pi := primeLimit / (math.Log(primeLimit) - 1)
		// 生成的素数从11开始（二进制），因此我们只能使用其中的四分之一。
		pi /= 4
		// 使用因子2确保密钥生成在合理的时间内终止
		// 。
		pi /= 2
		if pi <= float64(nprimes) {
			return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
		}
	}

	primes := make([]*big.Int, nprimes)

NextSetOfPrimes:
	for {
		todo := bits
		// crypto/rand应该设置每个素数的前两位。因此每个素数的形式都是
		// p_i=2^bitlen（p_i）×0.11。。。（在基数2中）。
		// 乘积为：
		// P=2^todo×α
		// 其中α是形式为0.11的n次数的乘积。。。
		// 
		// 如果α<1/2（这可能发生在n次>2），我们需要
		// 移位以补偿丢失的位：平均值0.11。。。
		// 是7/8，所以todo+shift-NPREMES*log2（7/8）~=位-1/2 
		// 将给出良好的结果。
		if nprimes >= 7 {
			todo += (nprimes - 2) / 5
		}
		for i := 0; i < nprimes; i++ {
			var err error
			primes[i], err = rand.Prime(random, todo/(nprimes-i))
			if err != nil {
				return nil, err
			}
			todo -= primes[i].BitLen()
		}

		// 确保素数成对不相等。
		for i, prime := range primes {
			for j := 0; j < i; j++ {
				if prime.Cmp(primes[j]) == 0 {
					continue NextSetOfPrimes
				}
			}
		}

		n := new(big.Int).Set(bigOne)
		totient := new(big.Int).Set(bigOne)
		pminus1 := new(big.Int)
		for _, prime := range primes {
			n.Mul(n, prime)
			pminus1.Sub(prime, bigOne)
			totient.Mul(totient, pminus1)
		}
		if n.BitLen() != bits {
			// 对于nptime==2，这种情况永远不会发生，因为
			// crypto/rand应该设置每个素数中的前两位。
			// 对于NPTimes>2，我们希望这种情况不会经常发生。
			continue NextSetOfPrimes
		}

		priv.D = new(big.Int)
		e := big.NewInt(int64(priv.E))
		ok := priv.D.ModInverse(e, totient)

		if ok != nil {
			priv.Primes = primes
			priv.N = n
			break
		}
	}

	priv.Precompute()
	return priv, nil
}

// incCounter递增一个四字节的大端计数器。
func incCounter(c *[4]byte) {
	if c[3]++; c[3] != 0 {
		return
	}
	if c[2]++; c[2] != 0 {
		return
	}
	if c[1]++; c[1] != 0 {
		return
	}
	c[0]++
}

// mgf1XOR使用PKCS#1 v2中指定的MGF1函数
// 生成的掩码对字节进行异或。1.
func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
	var counter [4]byte
	var digest []byte

	done := 0
	for done < len(out) {
		hash.Write(seed)
		hash.Write(counter[0:4])
		digest = hash.Sum(digest[:0])
		hash.Reset()

		for i := 0; i < len(digest) && done < len(out); i++ {
			out[done] ^= digest[i]
			done++
		}
		incCounter(&counter)
	}
}

// ErrMessageTooLong在尝试加密
// 对于公钥的大小来说太大的消息时返回。
var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size")

func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
	e := big.NewInt(int64(pub.E))
	c.Exp(m, e, pub.N)
	return c
}

// EncryptOAEP使用RSA-OAEP加密给定的消息。
// 
// OAEP由一个用作随机预言的哈希函数参数化。
// 对给定消息的加密和解密必须使用相同的哈希函数
// 和sha256。New（）是一个合理的选择。
// 
// 将随机参数用作熵源，以确保对同一消息进行两次加密不会产生相同的密文。
// 
// label参数可能包含不会加密的任意数据，
// ，但它为消息提供了重要的上下文。例如，如果给定的
// 公钥用于加密两种类型的消息，则可以使用不同的标签
// 值来确保攻击者不能将用于一种目的的密文
// 用于另一种目的。如果不需要，它可以是空的。
// 
// 消息长度不能超过公共模的长度减去
// 哈希长度的两倍，再减去2。
func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, error) {
	if err := checkPub(pub); err != nil {
		return nil, err
	}
	hash.Reset()
	k := pub.Size()
	if len(msg) > k-2*hash.Size()-2 {
		return nil, ErrMessageTooLong
	}

	hash.Write(label)
	lHash := hash.Sum(nil)
	hash.Reset()

	em := make([]byte, k)
	seed := em[1 : 1+hash.Size()]
	db := em[1+hash.Size():]

	copy(db[0:hash.Size()], lHash)
	db[len(db)-len(msg)-1] = 1
	copy(db[len(db)-len(msg):], msg)

	_, err := io.ReadFull(random, seed)
	if err != nil {
		return nil, err
	}

	mgf1XOR(db, hash, seed)
	mgf1XOR(seed, hash, db)

	m := new(big.Int)
	m.SetBytes(em)
	c := encrypt(new(big.Int), pub, m)

	out := make([]byte, k)
	return c.FillBytes(out), nil
}

// ErrDecryption表示无法解密消息。
// 为了避免自适应攻击，它故意含糊其辞。
var ErrDecryption = errors.New("crypto/rsa: decryption error")

// ErrVerification表示无法验证签名。
// 为了避免自适应攻击，它故意含糊其辞。
var ErrVerification = errors.New("crypto/rsa: verification error")

// 预计算机执行一些计算，以加快将来的私钥操作
// 的速度。
func (priv *PrivateKey) Precompute() {
	if priv.Precomputed.Dp != nil {
		return
	}

	priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
	priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)

	priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
	priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)

	priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])

	r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
	priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
	for i := 2; i < len(priv.Primes); i++ {
		prime := priv.Primes[i]
		values := &priv.Precomputed.CRTValues[i-2]

		values.Exp = new(big.Int).Sub(prime, bigOne)
		values.Exp.Mod(priv.D, values.Exp)

		values.R = new(big.Int).Set(r)
		values.Coeff = new(big.Int).ModInverse(r, prime)

		r.Mul(r, prime)
	}
}

// decrypt执行RSA解密，得到一个明文整数。如果给定
// 随机源，则使用RSA盲法。
func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
	// TODO（agl）：我们可以不使用百叶窗吗？
	if c.Cmp(priv.N) > 0 {
		err = ErrDecryption
		return
	}
	if priv.N.Sign() == 0 {
		return nil, ErrDecryption
	}

	var ir *big.Int
	if random != nil {
		randutil.MaybeReadByte(random)

		// 已启用致盲功能。盲操作包括将c乘以r^e。
		// 然后解密操作执行（m^e*r^e）^d mod n 
		// 等于mr mod n。然后，通过乘以r的乘法逆，r的因子可以被去除。
		// n！=0 

		var r *big.Int
		ir = new(big.Int)
		for {
			r, err = rand.Int(random, priv.N)
			if err != nil {
				return
			}
			if r.Cmp(bigZero) == 0 {
				r = bigOne
			}
			ok := ir.ModInverse(r, priv.N)
			if ok != nil {
				break
			}
		}
		bigE := big.NewInt(int64(priv.E))
		cCopy := new(big.Int).Set(c)
		cCopy.Mul(cCopy, rpowe)
		cCopy.Mod(cCopy, priv.N)
		c = cCopy
	}

	if priv.Precomputed.Dp == nil {
		m = new(big.Int).Exp(c, priv.D, priv.N)
	} else {
		// 我们有CRT所需的预计算值。解盲。
		m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
		m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
		m.Sub(m, m2)
		if m.Sign() < 0 {
			m.Add(m, priv.Primes[0])
		}
		m.Mul(m, priv.Precomputed.Qinv)
		m.Mod(m, priv.Primes[0])
		m.Mul(m, priv.Primes[1])
		m.Add(m, m2)

		for i, values := range priv.Precomputed.CRTValues {
			prime := priv.Primes[2+i]
			m2.Exp(c, values.Exp, prime)
			m2.Sub(m2, m)
			m2.Mul(m2, values.Coeff)
			m2.Mod(m2, prime)
			if m2.Sign() < 0 {
				m2.Add(m2, prime)
			}
			m2.Mul(m2, values.R)
			m.Add(m, m2)
		}
	}

	if ir != nil {
		m.Mul(m, ir)
		m.Mod(m, priv.N)
	}

	return
}

func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
	m, err = decrypt(random, priv, c)
	if err != nil {
		return nil, err
	}

	// 为了防止CRT计算中的错误，m^e是
	// 计算的，它应该与原始密文匹配。
	check := encrypt(new(big.Int), &priv.PublicKey, m)
	if c.Cmp(check) != 0 {
		return nil, errors.New("rsa: internal error")
	}
	return m, nil
}

// DecryptOAEP使用RSA-OAEP解密密文。
// 
// OAEP由一个用作随机预言的哈希函数参数化。
// 给定消息的加密和解密必须使用相同的哈希函数
// 和sha256。New（）是一个合理的选择。
// 
// 如果不为零，则使用随机参数对私钥操作
// 进行盲处理，避免定时侧通道攻击。这个
// 函数纯粹是内部的盲操作——随机数据不需要与加密时使用的数据匹配。
// 
// 标签参数必须与加密时给定的值匹配。详见
// EncryptOAEP。
func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, error) {
	if err := checkPub(&priv.PublicKey); err != nil {
		return nil, err
	}
	k := priv.Size()
	if len(ciphertext) > k ||
		k < hash.Size()*2+2 {
		return nil, ErrDecryption
	}

	c := new(big.Int).SetBytes(ciphertext)

	m, err := decrypt(random, priv, c)
	if err != nil {
		return nil, err
	}

	hash.Write(label)
	lHash := hash.Sum(nil)
	hash.Reset()

	// 我们可能泄漏了前导零的数量。
	// 目前尚不清楚我们是否能对此采取任何措施。
	em := m.FillBytes(make([]byte, k))

	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)

	seed := em[1 : hash.Size()+1]
	db := em[hash.Size()+1:]

	mgf1XOR(seed, hash, db)
	mgf1XOR(db, hash, seed)

	lHash2 := db[0:hash.Size()]

	// 我们必须在固定时间内验证明文，以避免像：J.Manger这样的攻击。对PKCS#1 
	// 非对称加密填充（OAEP）的选择密文攻击。0.In J.Kilian，《密码学进展》编辑。
	// v2中标准化的RSA最优
	lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)

	// 纯文本的剩余部分必须为零或多个0x00，后跟
	// 和0x01，后跟消息。
	// 查找索引：1如果我们仍在查找0x01 
	// 索引：第一个0x01字节的偏移量
	// 无效：1如果我们在0x01之前看到一个非零字节。
	var lookingForIndex, index, invalid int
	lookingForIndex = 1
	rest := db[hash.Size():]

	for i := 0; i < len(rest); i++ {
		equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
		equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
		index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
		lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
		invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
	}

	if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
		return nil, ErrDecryption
	}

	return rest[index+1:], nil
}
